The recent rise in popularity of social networks, such as Facebook of Palo Alto, Calif., and MySpace of Santa Monica, Calif., has created large quantities of data about interactions of individuals within such networks. The data is often organized and kept in records for ease of access by multiple users or applications. When the data is organized in electronically accessible records, it is managed and updated by computers. These electronically accessible records can be stored into operational databases. Users and applications can then query these operational databases to access the data. However, the data contain many private details about individuals. The network service provider may then be expected to anonymize the data prior to making it more widely available for users, e.g., for scientific research. One method for anonymizing the graph data is removing all non-graph information and adding or deleting some edges. Since social network data is richer in details about the users and their interactions, loss of details due to anonymization limits the usability of the data for analysis.